#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"
#include "TypeDefin.h"

using namespace std;
//效率很低 有提醒说记录父亲节点 自己似乎写了一个小时感觉
unordered_map<TreeNode *, TreeNode *> mp;
unordered_map<TreeNode *, bool> used;

void fill_map(TreeNode *root, TreeNode *parent) {
    if (!root)
        return;

    mp[root] = parent;
    fill_map(root->left, root);
    fill_map(root->right, root);
}

vector<int> res;

bool findTree(TreeNode *root, TreeNode *tar, int k, int now) {
    if (now > k || !root || used[root])
        return false;
    used[root] = true;
    if (k == now && tar == root) {
        used[root] = false;
        return true;
    }

    if (findTree(root->left, tar, k, now + 1) || findTree(root->right, tar, k, now + 1)
        || findTree(mp[root], tar, k, now + 1)) {
        used[root] = false;
        return true;
    }

    used[root] = false;
    return false;
}

void dfs(TreeNode *root, TreeNode *target, int k) {
    if (!root)
        return;

    // 递归寻找

    if (findTree(root, target, k, 0)) {
        res.push_back(root->val);
    }
    dfs(root->left, target, k);
    dfs(root->right, target, k);

}

vector<int> distanceK(TreeNode *root, TreeNode *target, int k) {

    fill_map(root, NULL);//填充map

    dfs(root, target, k);

    return res;


}